package week_five;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class MergeIntervals_56 {
    public int[][] merge(int[][] intervals) {
        //双关键字排序
//        Arrays.sort(intervals, new Comparator<int[]>() {
//            @Override
//            public int compare(int[] o1, int[] o2) {
//                return o1[0] != o1[0] ? o1[0] - o1[0] : o1[1] - o1[1];
//            }
//        });

        Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        //合并有序区间
        List<int[]> ans = new ArrayList<>();
        int left = -1;
        int far = -1;
        for (int[] cur: intervals){
            int start = cur[0];
            int end = cur[1];
            if(start<=far){
                far = Math.max(far, end);
            }else {
                if(far>=0)
                    ans.add(new int[]{left, far});
                left = start;
                far = end;
            }
        }
        if(far>=0)
            ans.add(new int[]{left, far});
        return ans.toArray(new int[ans.size()][]);
    }
}
